package com.wm.algorithm.bitmap;

/**
 * @ClassName: MediumBitMap
 * @Description: 中等级位图
 * @Author: WM
 * @Date: 2023/11/3 11:17
 */
public class MediumBitMap {

    /**
     * 从1亿个数字中取出最大的k个数字
     * 方法：位图排序
     * 思路：利用空间换时间的方法。首先找到给定数组中最大的数字，然后，建立这个最大值长度的位图数组，然后再去遍历给定的数组，
     * 根据每个元素的值作为索引，将位图数组中对应的值置为1，最后遍历位图数组，找到值为1的元素，就是最大的k个数字
     * 注意：这里要是提出内存有限的问题，用堆实现
     *
     * @param inputArray
     * @return
     */
    public int[] getTopK(int[] inputArray, int k) {
        int maxValue = Integer.MIN_VALUE;
        for (int i = 0; i < inputArray.length; i++) {
            if (inputArray[i] > maxValue) {
                maxValue = inputArray[i];
            }
        }

        int[] bitMap = new int[maxValue + 1];
        for (int i = 0; i < inputArray.length; i++) {
            // 数值位置的索引是有这个值，置1
            bitMap[inputArray[i]] = 1;
        }

        int[] result = new int[k];
        int index = 0;
        // 倒序遍历，因为result数组已经是排好序的了
        for (int i = maxValue; i >= 0 && index < k; i--) {
            if (bitMap[i] == 1) {
                result[index++] = 1;
            }
        }
        return result;
    }
}
